The present invention relates to a bridge for interconnecting networks, that is, an apparatus for interconnecting networks such as a Local Area Network (hereinafter referred to as a "LAN").
The operation and the function of a conventional LAN interconnecting bridge are discussed, for example, in IEEE Network vol. 2, No. 1, pp. 5-9, pp. 10-15, 1988.
Further, a circuit disclosed in JP-A No. 60-152145 for instance is known as an example of another LAN interconnecting bridge. This circuit is composed in such a manner that two LAN interface circuits and a data processor are coupled by means of a 3 port buffer memory, and necessity of transit or forwarding of frames received at above-described buffer memory from a LAN on one side is judged by checking a destination Media Access Control (MAC) address using an address check control unit, and when forwarding is required, that is, when the destination does not exist in the LAN on the side of receiving the frames, the frames are transmitted to another LAN. In the above-described check control circuit, there is provided a table which is formed by learning from source addresses of the received frames for storing a list of MAC addresses of stations connected to respective LANs. As a registration/deletion/search system for this table, a binary search scheme by means of hardwares is used.
In addition, as other prior arts related to address check, techniques such as disclosed in JP-A Nos. 63-138831 and 63-20626 - 20628 have been known. The former is a system in which an address information storage table and a hash function memory which stores a plurality of hash functions for obtaining table entry numbers from addresses are provided, and a processor performs reference to this hash function memory and reference/renewal or update of the address storing table, thereby to perform check/registration of addresses. In the latter, a string search device is used for the address storing table.
Among above-described prior arts, the first circuit using 3 port buffer memory perform address check for judging necessity for forwarding received frames by using the binary search scheme by means of hardwares. Therefore, search processing takes time. Furthermore, since it is required to sort table entry in advance, a processing to shift the entries behind the entry number which is newly registered in the rear of the table is required at the time of entry registration, and further, a processing to place the entries behind the relevant entry close frontward is required at the time of entry deletion. Because of such reasons, there is a problem that address check and processing of maintenance and management of the address information storage table take time, thus lowering frame forwarding performance of the bridge.
In the second system using a hash memory in which a plurality of hash functions are stored, the hash function which is used is altered by varying the capacity of the address information storage table in accordance with the variation of the number of the registered entries of the address information table. Therefore, registration processing of information having been stored in the table is required again depending on the variation of the number of the registered entries. Furthermore, the hash function memory and the entry registration table are separated and all of processings of search/comparison/deletion/registration have to be performed by means of softwares. Thus, there is a problem that the overhead becomes large and frame forwarding performance of the bridge is lowered.
Also, in a third technique in which a string search device is used for the address storage table, all the processings of search/comparison/deletion/registration are executed by means of hardwares. In this case, since comparison among a plurality of entries is executed successively with one comparator, there is a problem that processing takes time and it is also difficult to prepare the table of a large capacity.